package leetcode.tree;

/**
 * @author wangmaolin1
 * @date 2021/12/26 下午7:08
 */
public class _110平衡二叉树 {
    /**
     * 注意点：平衡二叉树的定义是，每个节点的左右子树的绝对值都不超过1
     * 自顶向下
     * @param root
     * @return
     */
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int left = height(root.left);
        int right = height(root.right);
        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private static int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }
    public static boolean isBalanced2(TreeNode root) {
        if (root==null){
            return true;
        }
        return recur(root)!=-1;
    }

    private static int recur(TreeNode root) {
        if (root==null){
            return 0;
        }
        int left=recur(root.left);
        if (left==-1){
            return left;
        }
        int right=recur(root.right);
        if (right==-1){
            return right;
        }
        return Math.abs(left-right)<=1?Math.max(left,right):-1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.right = new TreeNode(4);
        System.out.println(isBalanced(root));
    }
}
